Three-dimensional (3D) sensors based on structured light, laser scanning, or time of flight are used in many applications in robotics, computer vision, and computer graphics. The sensors scan a 3D scene as a set of 3D points, commonly referred to as a 3D point cloud. 3D point clouds for large scale scenes can be obtained by registering several scans acquired by the 3D sensors into a single coordinate system.
Storing and processing 3D point clouds require substantial memories and computational resources because each 3D point has to be stored and processed separately. Representing 3D point clouds as a set of primitive shapes is desired for compact modeling and fast processing.
One method fits primitive shapes to 3D point clouds using a random sample consensus (RANSAC) framework. That method hypothesizes several primitive, shapes and selects the best primitive shape according to scores of the hypothesized primitive shapes. That method uses raw 3D point clouds for determining the scores, which requires, for each hypothesized primitive shape, traversing all the points in the 3D point cloud or searching nearby points in the 3D point cloud given a reference point on the hypothesized primitive shape. This is time consuming.